package main

import (
	"fmt"
)

// 栅栏涂色
func main() {
	res := numWays(3, 3)
	fmt.Println(res)
}

// 时间: 0ms
// 内存: 2M 优化不掉
// n个柱子　k种颜料，最多只能两个两个相邻柱子颜色一样
func numWays(n int, k int) int {
	if n <= 0 || k <= 0 {
		return 0
	}

	if n == 1 {
		return k
	}

	if n == 2 {
		return k * k
	}

	lastTwoStep := k
	lastOneStep := k * k

	nowRes := 0
	for i := 2; i < n; i++ {
		nowRes = (lastOneStep + lastTwoStep) * (k - 1)
		lastTwoStep = lastOneStep
		lastOneStep = nowRes
	}

	return nowRes
}
